import pandas as pd
from collections import defaultdict


class FastDTW:

    @staticmethod
    def fast_dtw(x, y, radius=1, dist=lambda a, b: abs(a - b)):
        min_time_size = radius + 2

        if len(x) < min_time_size or len(y) < min_time_size:
            return FastDTW.dtw(x, y, dist=dist)

        x_shrinked = FastDTW.reduce_by_half(x)
        y_shrinked = FastDTW.reduce_by_half(y)
        distance, path = FastDTW.fast_dtw(x_shrinked, y_shrinked, radius=radius, dist=dist)
        window = FastDTW.__expand_window(path, len(x), len(y), radius)
        return FastDTW.dtw(x, y, window, dist=dist)

    @staticmethod
    def dtw(x, y, window=None, dist=lambda a, b: abs(a - b)):
        len_x, len_y = len(x), len(y)
        if window is None:
            window = [(i, j) for i in range(len_x) for j in range(len_y)]
        window = ((i + 1, j + 1) for i, j in window)
        D = defaultdict(lambda: (float('inf'),))
        D[0, 0] = (0, 0, 0)
        for i, j in window:
            dt = dist(x[i - 1], y[j - 1])
            D[i, j] = min((D[i - 1, j][0] + dt, i - 1, j), (D[i, j - 1][0] + dt, i, j - 1),
                          (D[i - 1, j - 1][0] + dt, i - 1, j - 1), key=lambda a: a[0])
        path = []
        i, j = len_x, len_y
        while not (i == j == 0):
            path.append((i - 1, j - 1))
            i, j = D[i, j][1], D[i, j][2]
        path.reverse()
        return D[len_x, len_y][0], path

    @staticmethod
    def __expand_window(path, len_x, len_y, radius):
        path_ = set(path)
        for i, j in path:
            for a, b in ((i + a, j + b)
                         for a in range(-radius, radius + 1)
                         for b in range(-radius, radius + 1)):
                path_.add((a, b))

        window_ = set()
        for i, j in path_:
            for a, b in ((i * 2, j * 2), (i * 2, j * 2 + 1),
                         (i * 2 + 1, j * 2), (i * 2 + 1, j * 2 + 1)):
                window_.add((a, b))

        window = []
        start_j = 0
        for i in range(0, len_x):
            new_start_j = None
            for j in range(start_j, len_y):
                if (i, j) in window_:
                    window.append((i, j))
                    if new_start_j is None:
                        new_start_j = j
                elif new_start_j is not None:
                    break
            start_j = new_start_j

        return window

    @staticmethod
    def reduce_by_half(x):

        x_reduce = []
        lens = len(x)
        for i in range(0, lens, 2):
            if (i+1) >= lens:
                half = x[i]
            else:
                half = (x[i] + x[i + 1]) / 2
            x_reduce.append(half)
        return x_reduce


aa = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# aa = []
# aa = [1]
# aa = [1, 2]
print(FastDTW.reduce_by_half(aa))


xx = [1, 2, 3, 2, 1, 4.5, 7, 6, 5, 7, 8, 9, 10]
yy = [4, 5, 6, 2, 1, 4.5, 4.5, 4.5, 8, 9, 5, 4, 4, 5, 4]
yy = [1, 2, 3, 1, 1, 4.5, 7, 6, 5, 7, 8, 9, 10]

distance, pair_part = FastDTW.fast_dtw(xx, yy)
print(distance)
for e in pair_part:
    print(e)


# ============================== Try =====================================
# sub_geo = 'RUSSIA/CIS'  # 'NA'
geo = 'NA'
business_type = 'Consumer'  # 'Commercial'
# year_range = 2014
# holiday_black = india_diwali_start
# holiday_red = india_diwali_end
# ------------------- start reading -------------------------------------------
df = pd.read_csv('D:/!Python/helloworld2/feature_data_20171113_1_2.csv')
values = {'geo': 'NA', 'sub_geo': 'NA', 'date': '1989-01-01', 'original_quantity': 1}
df = df.fillna(value=values)

df = df[df['geo'] == geo]
# df = df[df['sub_geo'] == sub_geo]
df = df[df['business_type'] == business_type]

print(df)
df = df[['sub_geo', 'family_desc', 'geo', 'group_id', 'date', 'original_quantity', 'business_type']]